import edu.princeton.cs.algs4.BinaryStdIn;
import edu.princeton.cs.algs4.BinaryStdOut;

import java.util.Arrays;
import java.util.LinkedList;

public class BurrowsWheeler {

    // apply Burrows-Wheeler transform,
    // reading from standard input and writing to standard output
    public static void transform() {
        String str = BinaryStdIn.readString();
        int len = str.length();
        CircularSuffixArray array = new CircularSuffixArray(str);
        int first = 0;
        for (int i = 0; i < array.length(); i++) {
            if (array.index(i) == 0) {
                first = i;
                break;
            }
        }
        BinaryStdOut.write(first);
        for (int i = 0; i < array.length(); i++) {
            BinaryStdOut.write(str.charAt((array.index(i) + 11) % 12), 8);
        }
        BinaryStdOut.close();
    }

    // apply Burrows-Wheeler inverse transform,
    // reading from standard input and writing to standard output
    public static void inverseTransform() {
        int first = BinaryStdIn.readInt();
        LinkedList<Character> list = new LinkedList<>();
        while (!BinaryStdIn.isEmpty()) {
            char c = BinaryStdIn.readChar(8);
            list.add(c);
        }

        char[] t = new char[list.size()];
        int len = 0;
        for (char c : list) {
            t[len++] = c;
        }

        char[] st = Arrays.copyOf(t, len);
        Arrays.sort(st);

        int[] next = new int[len];
        boolean[] flag = new boolean[len];


        for (int i = 0; i < len; i++) {
            char c = st[i];
            for (int j = 0; j < len; j++) {
                if (t[j] == c && !flag[j]) {
                    flag[j] = true;
                    next[i] = j;
                    break;
                }
            }
        }

        int start = first;
        do {
            BinaryStdOut.write(st[start]);
            start = next[start];
        }
        while (start != first);
        BinaryStdOut.close();
    }

    // if args[0] is "-", apply Burrows-Wheeler transform
    // if args[0] is "+", apply Burrows-Wheeler inverse transform
    public static void main(String[] args) {
        if (args[0].equals("-")) {
            transform();
        } else {
            if (!args[0].equals("+")) {
                throw new IllegalArgumentException("Illegal command line argument");
            }
            inverseTransform();
        }
    }
}
